{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sequence Reconstruction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sequenceReconstruction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #序列重建"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，其中 <code>nums</code> 是范围为 <code>[1，n]</code> 的整数的排列。还提供了一个 2D 整数数组&nbsp;<code>sequences</code>&nbsp;，其中&nbsp;<code>sequences[i]</code>&nbsp;是&nbsp;<code>nums</code>&nbsp;的子序列。<br />\n",
    "检查 <code>nums</code> 是否是唯一的最短&nbsp;<strong>超序列</strong> 。最短 <strong>超序列</strong> 是 <strong>长度最短</strong> 的序列，并且所有序列&nbsp;<code>sequences[i]</code>&nbsp;都是它的子序列。对于给定的数组&nbsp;<code>sequences</code>&nbsp;，可能存在多个有效的 <strong>超序列</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，对于&nbsp;<code>sequences = [[1,2],[1,3]]</code>&nbsp;，有两个最短的 <strong>超序列</strong> ，<code>[1,2,3]</code> 和 <code>[1,3,2]</code> 。</li>\n",
    "\t<li>而对于&nbsp;<code>sequences = [[1,2],[1,3],[1,2,3]]</code>&nbsp;，唯一可能的最短 <strong>超序列</strong> 是 <code>[1,2,3]</code> 。<code>[1,2,3,4]</code> 是可能的超序列，但不是最短的。</li>\n",
    "</ul>\n",
    "\n",
    "<p><em>如果 <code>nums</code> 是序列的唯一最短 <strong>超序列</strong> ，则返回 <code>true</code> ，否则返回 <code>false</code> 。</em><br />\n",
    "<strong>子序列</strong> 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], sequences = [[1,2],[1,3]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>有两种可能的超序列：[1,2,3]和[1,3,2]。\n",
    "序列 [1,2] 是[<u><strong>1,2</strong></u>,3]和[<u><strong>1</strong></u>,3,<u><strong>2</strong></u>]的子序列。\n",
    "序列 [1,3] 是[<u><strong>1</strong></u>,2,<u><strong>3</strong></u>]和[<u><strong>1,3</strong></u>,2]的子序列。\n",
    "因为 nums 不是唯一最短的超序列，所以返回false。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], sequences = [[1,2]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>最短可能的超序列为 [1,2]。\n",
    "序列 [1,2] 是它的子序列：[<u><strong>1,2</strong></u>]。\n",
    "因为 nums 不是最短的超序列，所以返回false。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>最短可能的超序列为[1,2,3]。\n",
    "序列 [1,2] 是它的一个子序列：[<strong>1,2</strong>,3]。\n",
    "序列 [1,3] 是它的一个子序列：[<u><strong>1</strong></u>,2,<u><strong>3</strong></u>]。\n",
    "序列 [2,3] 是它的一个子序列：[1,<u><strong>2,3</strong></u>]。\n",
    "因为 nums 是唯一最短的超序列，所以返回true。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;是&nbsp;<code>[1, n]</code>&nbsp;范围内所有整数的排列</li>\n",
    "\t<li><code>1 &lt;= sequences.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= sequences[i].length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= sum(sequences[i].length) &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= sequences[i][j] &lt;= n</code></li>\n",
    "\t<li><code>sequences</code>&nbsp;的所有数组都是 <strong>唯一 </strong>的</li>\n",
    "\t<li><code>sequences[i]</code>&nbsp;是&nbsp;<code>nums</code> 的一个子序列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sequence-reconstruction](https://leetcode.cn/problems/sequence-reconstruction/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sequence-reconstruction](https://leetcode.cn/problems/sequence-reconstruction/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n[[1,2],[1,3]]', '[1,2,3]\\n[[1,2]]', '[1,2,3]\\n[[1,2],[1,3],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 唯一的 最短的 超级序列\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        degrees = [0 for _ in range(n + 1)]\n",
    "        for ele in sequences:\n",
    "            for i in range(len(ele) - 1):\n",
    "                degrees[ele[i+1]] += 1\n",
    "                g[ele[i]].append(ele[i+1])\n",
    "        index = 0\n",
    "        q = []\n",
    "        for i in range(1, n + 1):\n",
    "            if degrees[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            if len(q) != 1 or q[0] != nums[index]:\n",
    "                return False\n",
    "            index += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                for y in g[x]:\n",
    "                    degrees[y] -= 1\n",
    "                    if degrees[y] == 0:\n",
    "                        q.append(y)\n",
    "        return index == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "      # 基于入度的拓扑排列\n",
    "      n=len(nums)\n",
    "      # 1-index\n",
    "      graph=[[] for _ in range(n+1)]\n",
    "      indegree=[0]*(n+1)\n",
    "      for s in sequences:\n",
    "        for x,y in pairwise(s):\n",
    "          indegree[y]+=1\n",
    "          graph[x].append(y)\n",
    "      \n",
    "      q=deque([i for i in range(1,n+1) if indegree[i]==0])\n",
    "\n",
    "      while q:\n",
    "        if len(q)>1:\n",
    "          return False\n",
    "        i=q.popleft()\n",
    "        for child in graph[i]:\n",
    "          indegree[child]-=1\n",
    "          if indegree[child]==0:\n",
    "            q.append(child)\n",
    "      \n",
    "      return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # if len(nums) ==1:\n",
    "        #     if nums[0] == sequences[0][0]:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)] #也可以用字典 这里使用了二维数组，每个一维数组中放入了 该索引对应节点的子节点\n",
    "        \n",
    "        indegree = [ 0 ] *n\n",
    "        for k in sequences:\n",
    "            for x,y in pairwise(k):\n",
    "                g[x-1].append(y-1)\n",
    "                indegree[y-1] +=1\n",
    "\n",
    "        #cnt = collections.Counter(indegree)\n",
    "        que = collections.deque()\n",
    "        #print(g,indegree)\n",
    "        # if cnt > 2:\n",
    "        #     return False\n",
    "        for i,d in enumerate(indegree):\n",
    "            if d == 0:\n",
    "                que.append(i)\n",
    "        while que:\n",
    "            if len(que) > 1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for j in g[curr]:\n",
    "                    #if j[0] == curr:\n",
    "                    indegree[j] -=1\n",
    "    \n",
    "                    if indegree[j] == 0:\n",
    "                        que.append(j)\n",
    "        return True\n",
    "            \n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n=len(nums)+1\n",
    "        dt=[[] for i in range(n)]\n",
    "        inD=[0]*n\n",
    "        for s in sequences:\n",
    "            for x in range(len(s)-1):\n",
    "                i=s[x]\n",
    "                j=s[x+1]\n",
    "                inD[j]+=1\n",
    "                dt[i].append(j)\n",
    "        q=[]\n",
    "        for i in range(1,n):\n",
    "            if inD[i]==0:\n",
    "                q.append(i)\n",
    "\n",
    "        while(q):\n",
    "            print(q)\n",
    "            if len(q)>1:\n",
    "                return False\n",
    "            xq=q.pop()\n",
    "            nx=dt[xq]\n",
    "            for i in nx:\n",
    "                inD[i]-=1\n",
    "                if inD[i]==0:\n",
    "                    q.append(i)\n",
    "        return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        #建图后看拓扑排序的结果是否唯一,就可以确定是否nums为唯一序列\n",
    "        n=len(nums)\n",
    "        degree=[0]*n\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for seq in sequences:\n",
    "            for u,v in pairwise(seq):\n",
    "                graph[u-1].append(v-1)\n",
    "                degree[v-1]+=1\n",
    "        quene=[]\n",
    "        for node in nums:\n",
    "            if degree[node-1]==0:\n",
    "                quene.append(node)\n",
    "        while quene:\n",
    "            if len(quene)>1:\n",
    "                return False\n",
    "            node=quene.pop(0)\n",
    "            for j in graph[node-1]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==0:\n",
    "                    quene.append(j)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # build relative orders\n",
    "        degrees = {}\n",
    "        neighbors = {}\n",
    "        for seq in sequences:\n",
    "            for idx in range(len(seq) - 1):\n",
    "                # seq[idx] -> seq[idx + 1]\n",
    "                if seq[idx + 1] not in degrees:\n",
    "                    degrees[seq[idx + 1]] = 1\n",
    "                else:\n",
    "                    degrees[seq[idx + 1]] += 1\n",
    "                if seq[idx] not in neighbors:\n",
    "                    neighbors[seq[idx]] = [seq[idx + 1]]\n",
    "                else:\n",
    "                    neighbors[seq[idx]].append(seq[idx + 1])\n",
    "        \n",
    "        zereIndegrees = []\n",
    "        for num in nums:\n",
    "            if num not in degrees:\n",
    "                zereIndegrees.append(num)\n",
    "        \n",
    "        idx = 0\n",
    "        while zereIndegrees:\n",
    "            if len(zereIndegrees) > 1:\n",
    "                return False\n",
    "            curNum = zereIndegrees.pop()\n",
    "            if curNum != nums[idx]:\n",
    "                return False\n",
    "            idx += 1\n",
    "\n",
    "            if curNum not in neighbors:\n",
    "                continue\n",
    "            for neighbor in neighbors[curNum]:\n",
    "                degrees[neighbor] -= 1\n",
    "                if degrees[neighbor] == 0:\n",
    "                    zereIndegrees.append(neighbor)\n",
    "                    del degrees[neighbor]\n",
    "        \n",
    "        # travirse all the nodes\n",
    "        return len(degrees) == 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "build relation from subseq\n",
    "\n",
    "each pair (num[i], num[j]) i < j\n",
    "then  num[i] shuold appear earlier than nums[j] in nums\n",
    "\n",
    "topology sort\n",
    "# iter all the pairs in sequences, and get the relative order\n",
    "# perofrm topology sort, each time we only have 1 candidate, and the resutls shuold match nums \n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        #建图后看拓扑排序的结果是否唯一\n",
    "        n=len(nums)\n",
    "        degree=[0]*n\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for seq in sequences:\n",
    "            for u,v in pairwise(seq):\n",
    "                graph[u-1].append(v-1)\n",
    "                degree[v-1]+=1\n",
    "        quene=[]\n",
    "        for node in nums:\n",
    "            if degree[node-1]==0:\n",
    "                quene.append(node)\n",
    "        while quene:\n",
    "            if len(quene)>1:\n",
    "                return False\n",
    "            node=quene.pop(0)\n",
    "            for j in graph[node-1]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==0:\n",
    "                    quene.append(j)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        g = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        deg = [0] * (n + 1)\n",
    "        for a in sequences:\n",
    "            for u, v in pairwise(a):\n",
    "                g[u].append(v)\n",
    "                deg[v] += 1\n",
    "        q = deque([i + 1 for i, x in enumerate(deg[1:]) if x == 0])\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        while q:\n",
    "            # print(f'{q},{deg}')\n",
    "            if len(q) > 1: return False\n",
    "            x = q.popleft()\n",
    "            ans.append(x)\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return nums == ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from itertools import pairwise\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 只需要判断sequences的每个序列构造超序列是否唯一\n",
    "        # 数字->结点，序列中的相邻结点间->有向边，等效于有向图的拓扑排序，计算每个结点的入度...\n",
    "        n = len(nums) \n",
    "        map1 = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for from_, to_ in pairwise(sequence): # pairwise用法：把[1, 2, 3, 4]拆成[1,2], [2,3], [3,4]\n",
    "                map1[from_ - 1].append(to_ - 1)\n",
    "                inDeg[to_ - 1] += 1\n",
    "        # ---------------------------------\n",
    "        q = deque()\n",
    "        for i, d in enumerate(inDeg):\n",
    "            if d == 0:\n",
    "                q.append(i)\n",
    "        # ----------------------------------\n",
    "\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            from_ = q.popleft()\n",
    "            for to_ in map1[from_]:\n",
    "                inDeg[to_] -= 1\n",
    "                if inDeg[to_] == 0:\n",
    "                    q.append(to_)\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x,y in pairwise(sequence):\n",
    "                g[x-1].append(y-1)\n",
    "                deg[y-1] += 1\n",
    "        q = deque([i for i, d in enumerate(deg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        deg = [0]*(n + 1)\n",
    "        g = defaultdict(list)\n",
    "        for s in sequences:\n",
    "            for x,y in pairwise(s):\n",
    "                g[x].append(y)\n",
    "                deg[y] += 1\n",
    "        q = deque()\n",
    "        for i in range(1,n + 1):\n",
    "            if deg[i] == 0:\n",
    "                q.append(i)\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            cur = q.popleft()\n",
    "            cnt += 1\n",
    "            for nx in g[cur]:\n",
    "                deg[nx] -= 1\n",
    "                if deg[nx] == 0:\n",
    "                    q.append(nx)\n",
    "        return cnt == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        relations = [[] for _ in range(n)]\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            indeg[num] = 0\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                if u not in indeg.keys():\n",
    "                    indeg[u] = 0\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key, value in indeg.items():\n",
    "            if value == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for u,v in itertools.pairwise(seq):\n",
    "                edges[u-1].append(v-1)\n",
    "                deg[v-1]+=1\n",
    "        \n",
    "        q = collections.deque([u for u in range(n) if deg[u]==0])\n",
    "        if len(q)>1:\n",
    "            return False\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            flag = False\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    if not flag:\n",
    "                        q.append(v)\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return n==len(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = collections.defaultdict(list)\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        for seq in sequences:\n",
    "            start = seq[0]\n",
    "            if start not in indeg.keys():\n",
    "                indeg[start] = 0\n",
    "            for i in range(len(seq)-1):\n",
    "                start, next = seq[i], seq[i+1]\n",
    "                edges[start].append(next)\n",
    "                indeg[next] += 1\n",
    "\n",
    "        q = collections.deque()\n",
    "\n",
    "        for node, indegree in indeg.items():\n",
    "            if indegree == 0:\n",
    "                q.append(node)\n",
    "        \n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for node in edges[u]:\n",
    "                indeg[node] -= 1\n",
    "                if indeg[node] == 0:\n",
    "                    q.append(node)\n",
    "        \n",
    "        if result != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            u = seq[0]\n",
    "            if u not in indeg.keys():\n",
    "                indeg[u] = 0\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key, value in indeg.items():\n",
    "            if value == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            u = seq[0]\n",
    "            if u not in indeg.keys():     # 考虑seq中的第一个元素！！！因为他们有可能只出现一次，从而不会被添加到字典中！\n",
    "                indeg[u] = 0\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key, value in indeg.items():\n",
    "            if value == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for u,v in itertools.pairwise(seq):\n",
    "                edges[u-1].append(v-1)\n",
    "                deg[v-1]+=1\n",
    "        \n",
    "        q = collections.deque([u for u in range(n) if deg[u]==0])\n",
    "        if len(q)>1:\n",
    "            return False\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            flag = False\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    if not flag:\n",
    "                        q.append(v)\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return n==len(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for u,v in itertools.pairwise(seq):\n",
    "                edges[u-1].append(v-1)\n",
    "                deg[v-1]+=1\n",
    "        \n",
    "        q = collections.deque([u for u in range(n) if deg[u]==0])\n",
    "        if len(q)>1:\n",
    "            return False\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            flag = False\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    if not flag:\n",
    "                        q.append(v)\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return n==len(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for u,v in itertools.pairwise(seq):\n",
    "                edges[u-1].append(v-1)\n",
    "                deg[v-1]+=1\n",
    "        \n",
    "        q = collections.deque([u for u in range(n) if deg[u]==0])\n",
    "        if len(q)>1:\n",
    "            return False\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            flag = False\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    if not flag:\n",
    "                        q.append(v)\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return n==len(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for u,v in itertools.pairwise(seq):\n",
    "                edges[u-1].append(v-1)\n",
    "                deg[v-1]+=1\n",
    "        \n",
    "        q = collections.deque([u for u in range(n) if deg[u]==0])\n",
    "        if len(q)>1:\n",
    "            return False\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            flag = False\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    if not flag:\n",
    "                        q.append(v)\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return n==len(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for u,v in itertools.pairwise(seq):\n",
    "                edges[u-1].append(v-1)\n",
    "                deg[v-1]+=1\n",
    "        \n",
    "        q = collections.deque([u for u in range(n) if deg[u]==0])\n",
    "        if len(q)>1:\n",
    "            return False\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            flag = False\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    if not flag:\n",
    "                        q.append(v)\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return n==len(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        #relations = [[] for _ in range(n)]\n",
    "        relations = collections.defaultdict(list)\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        #relations = [[] for _ in range(n)]\n",
    "        relations = collections.defaultdict(list)\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        outDegrees = [0] * (n + 1)\n",
    "        listAdj = [set() for _ in range(n + 1)]\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                v1, v2 = seq[i], seq[i + 1]\n",
    "                if v2 not in listAdj[v1]:\n",
    "                    listAdj[v1].add(v2)\n",
    "                    outDegrees[v2] += 1\n",
    "\n",
    "        queue = [i for i in range(1, n + 1) if outDegrees[i] == 0]\n",
    "        \n",
    "        while queue:\n",
    "            if len(queue) > 1:\n",
    "                return False\n",
    "            v1 = queue.pop(0)\n",
    "            for v2 in listAdj[v1]:\n",
    "                outDegrees[v2] -= 1\n",
    "                if outDegrees[v2] == 0:\n",
    "                    queue.append(v2)\n",
    "        \n",
    "        return len(queue) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        #relations = [[] for _ in range(n)]\n",
    "        relations = collections.defaultdict(list)\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        #relations = [[] for _ in range(n)]\n",
    "        relations = collections.defaultdict(list)\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[x, y] -> x is prerequisite of y\n",
    "we can only have one solution\n",
    "\n",
    "\"\"\"\n",
    "from collections import deque, defaultdict\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        all_nodes = set()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)):\n",
    "                all_nodes.add(seq[i])\n",
    "                if i + 1 < len(seq):\n",
    "                    graph[seq[i]].append(seq[i + 1])\n",
    "\n",
    "        def get_indegree(nodes):\n",
    "            counter = {node: 0 for node in nodes}\n",
    "            for node in nodes:\n",
    "                for neighbor in graph[node]:\n",
    "                    counter[neighbor] += 1\n",
    "            return counter\n",
    "\n",
    "        nodes = list(all_nodes)\n",
    "        indegrees = get_indegree(nodes)\n",
    "\n",
    "        queue = deque([node for node in nodes if indegrees[node] == 0])\n",
    "        topo_order = []\n",
    "\n",
    "        while queue:\n",
    "            # 如果说下一层有多个选择，说明最后的解不唯一\n",
    "            if len(queue) > 1:\n",
    "                return False\n",
    "\n",
    "            node = queue.popleft()\n",
    "            topo_order.append(node)\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                indegrees[neighbor] -= 1\n",
    "                if indegrees[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        \n",
    "        return True if nums == topo_order else False\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set(nums)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "                if u not in nodes or v not in nodes:\n",
    "                    return False\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        #relations = [[] for _ in range(n)]\n",
    "        relations = collections.defaultdict(list)\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0]* n\n",
    "        #relations = [[] for _ in range(n)]\n",
    "        relations = collections.defaultdict(list)\n",
    "        que = collections.deque()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for x,y in itertools.pairwise(seq):\n",
    "                relations[x-1].append(y-1)\n",
    "                indegree[y-1] += 1 \n",
    "        \n",
    "        print(indegree,relations)\n",
    "\n",
    "        for i,k in enumerate(indegree):\n",
    "            if k == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            if len(que) >1:\n",
    "                return False\n",
    "            else:\n",
    "                curr = que.popleft()\n",
    "                for a in relations[curr]:\n",
    "                    indegree[a] -=1\n",
    "                    if indegree[a] ==0:\n",
    "                        que.append(a)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        if len(sequences) == 1 and sequences[0] == nums:\n",
    "            return True\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set()\n",
    "        result = []\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                nodes.add(seq[i])\n",
    "                edges[seq[i]].append(seq[i+1])\n",
    "                indeg[seq[i+1]] += 1\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        if len(sequences) == 1 and sequences[0] == nums:\n",
    "            return True\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set(nums)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                if v not in edges[u]:\n",
    "                    edges[u].append(v)\n",
    "                    indeg[v] += 1\n",
    "                if u not in nodes or v not in nodes:\n",
    "                    return False\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "\n",
    "\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        all_node = set()\n",
    "        for i in sequences:\n",
    "            all_node.update(set(i))\n",
    "            for j in range(1, len(i)):\n",
    "                if i[j] not in relation[i[j - 1]]:\n",
    "                    indegree[i[j]] += 1\n",
    "                    relation[i[j - 1]].append(i[j])\n",
    "\n",
    "        zero = [x for x in all_node if x not in indegree]\n",
    "        # print(\"zero:\", zero)\n",
    "        res = []\n",
    "        while zero:\n",
    "            if len(zero) > 1:\n",
    "                return False\n",
    "            t = zero.pop()\n",
    "            res.append(t)\n",
    "            for i in relation.get(t, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    zero.append(i)\n",
    "\n",
    "        return res == nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        indegree = {idx: 0 for idx in range(1, len(nums) + 1)}\n",
    "        adjacent = {idx: [] for idx in range(1, len(nums) + 1)}\n",
    "\n",
    "        for seq_item in sequences:\n",
    "            for idx in range(len(seq_item) - 1):\n",
    "                pre = seq_item[idx]\n",
    "                cur = seq_item[idx + 1]\n",
    "                adjacent[pre].append(cur)\n",
    "                indegree[cur] += 1\n",
    "        \n",
    "        queue = deque()\n",
    "        for idx in indegree:\n",
    "            if indegree[idx] == 0:\n",
    "                queue.append(idx)\n",
    "\n",
    "        ret_list = []\n",
    "        \n",
    "        while queue:\n",
    "            if len(queue) > 1:\n",
    "                return False\n",
    "            idx = queue.pop()\n",
    "            ret_list.append(idx)\n",
    "            for next_idx in adjacent[idx]:\n",
    "                indegree[next_idx] -= 1\n",
    "                if indegree[next_idx] == 0:\n",
    "                    queue.append(next_idx)\n",
    "        \n",
    "        return ret_list == nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set(nums)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set(nums)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        adj_dict = defaultdict(list)\n",
    "        elements = set()\n",
    "        in_deg = defaultdict(int)\n",
    "        for sequence in sequences:\n",
    "            if sequence.__len__() == 1:\n",
    "                elements.add(sequence[0])\n",
    "\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                adj_dict[x].append(y)\n",
    "                elements.add(x)\n",
    "                elements.add(y)\n",
    "                in_deg[y] += 1\n",
    "        no_pre = set(elements)\n",
    "\n",
    "        if elements.__len__() != nums.__len__():\n",
    "            return False\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                try:\n",
    "                    no_pre.remove(y)\n",
    "                except KeyError:\n",
    "                    pass\n",
    "\n",
    "        ptr = 0\n",
    "        while no_pre:\n",
    "            if no_pre.__len__() != 1:\n",
    "                return False\n",
    "            c = no_pre.pop()\n",
    "            if nums[ptr] != c:\n",
    "                return False\n",
    "            ptr += 1\n",
    "            for next_node in adj_dict[c]:\n",
    "                in_deg[next_node] -= 1\n",
    "                if in_deg[next_node] == 0:\n",
    "                    no_pre.add(next_node)\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set(nums)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                edges[u].append(v)\n",
    "                indeg[v] += 1\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        nodes = set(nums)\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                u, v = seq[i], seq[i + 1]\n",
    "                if v not in edges[u]:\n",
    "                    edges[u].append(v)\n",
    "                    indeg[v] += 1\n",
    "                if u not in nodes or v not in nodes:\n",
    "                    return False\n",
    "            \n",
    "        result = []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for key in nodes:\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            u = q.popleft()\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if list(result) != nums:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        if nums == [1] and sequences == [[1]]:\n",
    "            return True\n",
    "\n",
    "        adj_dict = defaultdict(list)\n",
    "        elements = set()\n",
    "        in_deg = defaultdict(int)\n",
    "        for sequence in sequences:\n",
    "            # if sequence.__len__() == 1:\n",
    "            #     elements.add(sequence[0])\n",
    "\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                adj_dict[x].append(y)\n",
    "                elements.add(x)\n",
    "                elements.add(y)\n",
    "                in_deg[y] += 1\n",
    "        no_pre = set(elements)\n",
    "\n",
    "        if elements.__len__() != nums.__len__():\n",
    "            return False\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                try:\n",
    "                    no_pre.remove(y)\n",
    "                except KeyError:\n",
    "                    pass\n",
    "\n",
    "        ptr = 0\n",
    "        while no_pre:\n",
    "            if no_pre.__len__() != 1:\n",
    "                return False\n",
    "            c = no_pre.pop()\n",
    "            if nums[ptr] != c:\n",
    "                return False\n",
    "            ptr += 1\n",
    "            for next_node in adj_dict[c]:\n",
    "                in_deg[next_node] -= 1\n",
    "                if in_deg[next_node] == 0:\n",
    "                    no_pre.add(next_node)\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        adj_dict = defaultdict(list)\n",
    "        elements = set()\n",
    "        in_deg = defaultdict(int)\n",
    "        for sequence in sequences:\n",
    "            if sequence.__len__() == 1:\n",
    "                elements.add(sequence[0])\n",
    "\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                adj_dict[x].append(y)\n",
    "                elements.add(x)\n",
    "                elements.add(y)\n",
    "                in_deg[y] += 1\n",
    "        no_pre = set(elements)\n",
    "\n",
    "        if elements.__len__() != nums.__len__():\n",
    "            return False\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                try:\n",
    "                    no_pre.remove(y)\n",
    "                except KeyError:\n",
    "                    pass\n",
    "\n",
    "        ptr = 0\n",
    "        while no_pre:\n",
    "            if no_pre.__len__() != 1:\n",
    "                return False\n",
    "            c = no_pre.pop()\n",
    "            if nums[ptr] != c:\n",
    "                return False\n",
    "            ptr += 1\n",
    "            for next_node in adj_dict[c]:\n",
    "                in_deg[next_node] -= 1\n",
    "                if in_deg[next_node] == 0:\n",
    "                    no_pre.add(next_node)\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:\n",
    "        #----建图\n",
    "        us = set()\n",
    "        adjvex = collections.defaultdict(list)\n",
    "        indegree = collections.defaultdict(int)\n",
    "        for seq in seqs:\n",
    "            us.add(seq[0])\n",
    "            for i in range(len(seq) - 1):\n",
    "                x, y = seq[i], seq[i + 1]\n",
    "                adjvex[x].append(y)\n",
    "                indegree[y] += 1\n",
    "                us.add(y)\n",
    "        \n",
    "        #----如果数据不同，必不能\n",
    "        if us != set(org):\n",
    "            return False\n",
    "        \n",
    "        #----topsort()\n",
    "        path = []\n",
    "        q = collections.deque()\n",
    "        for x in us:\n",
    "            if x not in indegree:\n",
    "                q.append(x)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            path.append(x)\n",
    "            for y in adjvex[x]:\n",
    "                indegree[y] -= 1\n",
    "                if indegree[y] == 0:\n",
    "                    q.append(y)\n",
    "            \n",
    "        return path == org\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0] * (n + 1)\n",
    "        graph = [{} for _ in range(n + 1)]\n",
    "\n",
    "        # 初始化入度和图\n",
    "        for i in range(1, n + 1):\n",
    "            graph[i] = {}\n",
    "\n",
    "        for seq in sequences:\n",
    "            # 建立拓扑关系（偏序关系）\n",
    "            for i in range(1, len(seq)):\n",
    "                # 如果该依赖关系没有添加过则添加\n",
    "                from_num, to_num = seq[i - 1], seq[i]\n",
    "                if from_num < 1 or from_num > n or to_num < 0 or to_num > n:\n",
    "                    # 出现了不在范围内的字符，不是超序列\n",
    "                    return False\n",
    "                # 建立依赖，统计入度\n",
    "                if to_num not in graph[from_num]:\n",
    "                    graph[from_num][to_num] = {}\n",
    "                    indegree[to_num] += 1\n",
    "\n",
    "        # 拓扑排序\n",
    "        queue = []\n",
    "        for i in range(1, len(indegree)):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        i = 0\n",
    "        while queue:\n",
    "            if nums[i] != queue[0]:\n",
    "                # 排序不一致\n",
    "                return False\n",
    "\n",
    "            if len(queue) > 1:\n",
    "                # 任何时刻只能有一个入度为0的节点\n",
    "                return False\n",
    "\n",
    "            num = queue[0]\n",
    "            i += 1\n",
    "            queue = queue[1:]\n",
    "            # 减少后置节点入度\n",
    "            for key in graph[num]:\n",
    "                indegree[key] -= 1\n",
    "                if indegree[key] == 0:\n",
    "                    queue.append(key)\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        g=collections.defaultdict(set)\n",
    "        n=len(nums)\n",
    "        in_degree=[0]*(n+1)\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x].add(y)\n",
    "                in_degree[y] += 1\n",
    "        q=deque()\n",
    "        for i in range(1,n+1):\n",
    "            if in_degree[i]==0:\n",
    "                q.append(i)\n",
    "        res=set()\n",
    "        while q:\n",
    "            if len(q)>1:\n",
    "                return False\n",
    "            node=q.popleft()\n",
    "            res.add(node)    \n",
    "            for i in g[node]:\n",
    "                in_degree[i]-=1\n",
    "                if in_degree[i]==0:\n",
    "                    q.append(i)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        s1 = set(nums)\n",
    "        s2 = set()\n",
    "        pre_num = defaultdict(int)\n",
    "        pst_dict = defaultdict(list)\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)):\n",
    "                s2.add(seq[i])\n",
    "                if i > 0:\n",
    "                    pre_num[seq[i]] += 1\n",
    "                    pst_dict[seq[i-1]].append(seq[i])\n",
    "                \n",
    "        if s1 != s2:\n",
    "            return False\n",
    "        dq = deque()\n",
    "        for key in nums:\n",
    "            if pre_num[key] == 0:\n",
    "                dq.append(key)\n",
    "        \n",
    "        res = []\n",
    "        while dq:\n",
    "            if len(dq) > 1:\n",
    "                return False\n",
    "            tmp = dq.popleft()\n",
    "            res.append(tmp)\n",
    "            for data in pst_dict[tmp]:\n",
    "                pre_num[data] -= 1\n",
    "                if pre_num[data] == 0:\n",
    "                    dq.append(data)\n",
    "\n",
    "        s3 = set(res)\n",
    "        if s1 == s3:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        in_degrees = [0 for _ in range(n)]\n",
    "        g = defaultdict(set)\n",
    "        for s in sequences:\n",
    "            for a, b in zip(s, s[1: ]):\n",
    "                if b - 1 not in g[a - 1]:\n",
    "                    g[a - 1].add(b - 1)\n",
    "                    in_degrees[b - 1] += 1\n",
    "        s = set(i for i in range(n) if in_degrees[i] == 0)\n",
    "        l = 0\n",
    "        while len(s) == 1:\n",
    "            ns = set()\n",
    "            (u,) = s\n",
    "            for v in g[u]:\n",
    "                in_degrees[v] -= 1\n",
    "                if in_degrees[v] == 0:\n",
    "                    ns.add(v)\n",
    "            l += 1\n",
    "            s = ns\n",
    "        return l == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        in_degrees = [0 for _ in range(n)]\n",
    "        g = defaultdict(set)\n",
    "        for s in sequences:\n",
    "            for a, b in zip(s, s[1: ]):\n",
    "                if b - 1 not in g[a - 1]:\n",
    "                    g[a - 1].add(b - 1)\n",
    "                    in_degrees[b - 1] += 1\n",
    "        s = set(i for i in range(n) if in_degrees[i] == 0)\n",
    "        l = 0\n",
    "        while len(s) == 1:\n",
    "            ns = set()\n",
    "            (u,) = s\n",
    "            for v in g[u]:\n",
    "                in_degrees[v] -= 1\n",
    "                if in_degrees[v] == 0:\n",
    "                    ns.add(v)\n",
    "            l += 1\n",
    "            s = ns\n",
    "        return l == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        in_degrees = [0 for _ in range(n)]\n",
    "        g = defaultdict(set)\n",
    "        for s in sequences:\n",
    "            for a, b in zip(s, s[1: ]):\n",
    "                if b - 1 not in g[a - 1]:\n",
    "                    g[a - 1].add(b - 1)\n",
    "                    in_degrees[b - 1] += 1\n",
    "        s = [i for i in range(n) if in_degrees[i] == 0]\n",
    "        l = 0\n",
    "        while len(s) == 1:\n",
    "            u = s.pop()\n",
    "            for v in g[u]:\n",
    "                in_degrees[v] -= 1\n",
    "                if in_degrees[v] == 0:\n",
    "                    s.append(v)\n",
    "            l += 1\n",
    "        return l == n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
